Median of Two Sorted Arrays(LeetCode)

文章目录

1. 1. Question:Median of Two Sorted Arrays
2. 2. SourceCode:
   1. 2.1. s1
   2. 2.2. s2
   3. 2.3. 结论

Question:Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity 

should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

SourceCode:

s1

//笔者提交版本；耗时：ms；

//solutin1: 时间复杂度应该超了，但AC
//归并排序
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       double result = 0;
        
        int len1 = nums1.length;
        int len2 = nums2.length;
        
        
        int mid = (int)Math.ceil((len1+ len2)/2.0);
        int mergeLen = mid+1;//偶数中位数
        int[] mergeArray = new int[mergeLen];
        int k = 0,i = 0,j = 0;
        for(; k < mergeLen && (i<len1 && j<len2);){
            mergeArray[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++] ;
        }
        
        
        if(i ==len1){
        	while(k< mergeLen&&j<len2){
        		mergeArray[k++] = nums2[j++];
        	}
        }
        if(j ==len2){
        	while(k< mergeLen&&i<len1){
        		mergeArray[k++] = nums1[i++];
        	}
        }
        
        //debug
        //System.out.println(Arrays.toString(mergeArray));
        
        result = mergeArray[mid-1];
        int sum = len1+len2;
        if(sum%2 == 0){
            int resultBack  = mergeArray[mid];
            result = (result+resultBack)/2.0;
        }
        
        return result;
    }
}



//solution 2: 
//解题思路：

//该题可以解决所有求有序数组A和B有序合并之后第k小的数！

//该题的重要结论：

//如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中，可以用反证法证明。
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return findTheMedian(nums1,nums2);
    }
    
    
    private double findTheMedian(int num1[] ,int num2[]) {
		int totoal = num1.length + num2.length;
		int k = totoal/2 ;
		if(totoal % 2 == 0){
			 double result = findKthElement(k, num1, num2, 0, 0) + findKthElement(k+1, num1, num2, 0, 0);
			 return result/2.0;
		}else {
			return findKthElement(k+1, num1, num2, 0, 0);
		}
	}
	
	//找第Kth个数；*******！！！！！！！！！！！！！！*********
	private double findKthElement(int k, int num1[] ,int num2[],int start1,int start2){
		if(start1 >= num1.length){
			return num2[start2+k-1];
		}
		if(start2 >= num2.length){
			return num1[start1+k-1];
		}
		
		if(1 == k){
			return Math.min(num1[start1], num2[start2]);
		}
		
		//0~halfK共有k/2 个元素； 
		int halfK = k/2 - 1;
		int halfKOfnum1 = start1 + halfK;
		int halfKOfnum2 = start2 + halfK;
		
		/*
		 * !!!重要防止越界，当越界后，取最大值
		 * 越界意味着本数组元素不够，则不够的元素都应从另一个数组中获取；
		 * 之前另一数组取得halfk个元素均是合法的；
		 */
		int V1 = halfKOfnum1 < num1.length ? num1[halfKOfnum1] : Integer.MAX_VALUE;
		int V2 = halfKOfnum2 < num2.length ? num2[halfKOfnum2] : Integer.MAX_VALUE;
		
		/*int V1 = num1[halfKOfnum1];
		int V2 = num2[halfKOfnum2];*/
		
		if (V1 < V2) {
		                         //注意此处已找到k/2个元素，要找剩余元素，即k-k-k/2;
			return findKthElement(k-k/2, num1, num2, halfKOfnum1+1, start2);
		}else {
			return findKthElement(k-k/2, num1, num2, start1, halfKOfnum2+1);
		}
		
		
	}
}

s2

//该版本参考了Discuss,还没看Discuss；耗时：ms；
//待写

结论

该题可以解决所有求有序数组A和B有序合并之后第k小的数！

该题的重要结论：

如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中，可以用反证法证明。

详见上述代码solution2；找第Kth个数；